home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Taifun / Taifun 029 (1987-08-15)(Ossowski, Stefan)(DE)(PD).zip / Taifun 029 (1987-08-15)(Ossowski, Stefan)(DE)(PD).adf / Utilities / FComp / fcomp2.c < prev    next >
C/C++ Source or Header  |  1978-08-10  |  7KB  |  311 lines
  1. /* FCOMP.C - A File Comparison Program
  2.  *
  3.  * Source:      A File Comparison Program
  4.  *              Webb Miller and Eugene W. Myers
  5.  *              SOFTWARE - PRACTICE AND EXPERIENCE
  6.  *              Vol. 15(11), 1025-1040
  7.  *              November, 1985
  8.  *              Copyright John Wiley & Sons, Ltd.
  9.  *
  10.  * Usage:       fcomp [-n] file1 file2
  11.  *
  12.  *              where the optional flag "n" is an integer constant
  13.  *              that limits the size of edit scripts that will be
  14.  *              considered by fcomp. If all edit scripts changing
  15.  *              file1 to file2 contain more than "n" insertions
  16.  *              and deletions, then a message to that effect is
  17.  *              all that is printed. If no "n" is specified, then
  18.  *              arbitrarily long scripts may be considered.
  19.  */
  20.  
  21. /*** Include Files ***/
  22.  
  23. #include <stdio.h>
  24.  
  25. /*** Definitions ***/
  26.  
  27. #define MAXLINES  2000      /* Maximum # of lines in a file */
  28. #define ORIGIN    MAXLINES  /* Subscript for diagonal zero */
  29. #define INSERT    1
  30. #define DELETE    2
  31.  
  32. /*** Structures ***/
  33.  
  34. /* Edit scripts are stored in linked lists */
  35.  
  36. struct edit
  37. {
  38.   struct edit *link;    /* Previous edit command */
  39.   int op;               /* INSERT or DELETE */
  40.   int line1;            /* Line number in file1 */
  41.   int line2;            /* Line number in file2 */
  42. };
  43.  
  44. /*** Global Variables ***/
  45.  
  46. char *A[MAXLINES],      /* Ptrs. to lines of file1 and file2 */
  47.      *XB[MAXLINES];
  48.  
  49. /*** Main Body of Program ***/
  50.  
  51. int main(argc,argv)
  52. int argc;
  53. char **argv;
  54. {
  55.   int max_d,    /* Bound on size of edit script */
  56.       m,        /* Number of lines in file1 */
  57.       n2,        /* Number of lines in file2 */
  58.       lower,    /* Left-most diagonal under consideration */
  59.       upper,    /* Right-most diagonal under consideration */
  60.       d,        /* Current edit distance */
  61.       k,        /* Current diagonal */
  62.       row,      /* Row number */
  63.       col;      /* Column number */
  64.  
  65.   /* For each diagonal, two items are saved */
  66.  
  67.   int last_d[2*MAXLINES+1];     /* Row containing last d */
  68.   struct edit *script[2*MAXLINES+1];  /* Corresponding edit script */
  69.  
  70.   struct edit *new;
  71.   char *malloc();
  72.   void put_scr(),
  73.        fatal(),
  74.        exceed();
  75.  
  76.   if(argc > 1 && argv[1][0] == '-')
  77.   {
  78.     anotherline which should be found by fcomp
  79.     max_d = atoi(&argv[1][1]);
  80.     ++argv;
  81.     --argc;
  82.   }
  83.   else
  84.     max_d = 2*MAXLINES;
  85.  
  86.   if(argc != 3)
  87.     fatal("FCOMP requires two file names.");
  88.  
  89.   /* Read in file1 and file2 */
  90.  
  91.   m = in_file(argv[1],A);
  92.   n = in_file(argv[2],B);
  93.  
  94.   /* Initialize: 0 entries in D indicate identical prefixes */
  95.  
  96.   for(row = 0; row < m && row < n && strcmp(A[row],B[row]) == 0; ++row)
  97.     ;
  98.  
  99.   last_d[ORIGIN] = row;
  100.   script[ORIGIN] = NULL;
  101.   lower = (row == m) ? ORIGIN + 1 : ORIGIN - 1;
  102.   upper = (row == n) ? ORIGIN - 1 : ORIGIN + 1;
  103.   if(lower > upper)
  104.   {
  105.     puts("The files are identical.");
  106.     exit(0);
  107.   }
  108.  
  109.   /* For each value of the edit distance */
  110.  
  111.   for(d = 1; d <= max_d; ++d)
  112.   {
  113.     /* For each relevant diagonal */
  114.  
  115.     for(k = lower; k <= upper; k += 2)
  116.     {
  117.       /* Get space for next edit instruction */
  118.  
  119.       new = (struct edit *)malloc(sizeof(struct edit));
  120.       if(!new)
  121.         exceed(d);
  122.  
  123.       /* Find a d on diagonal k */
  124.  
  125.       if(k == ORIGIN-d || k != ORIGIN+d && last_d[k+1] >= last_d[k-1])
  126.       {
  127.         /* Moving down from the last d-1 on diagonal k+1 puts you
  128.          * farther along diagonal k than does moving right from the
  129.          * last d-1 on diagonal k-1.
  130.          */
  131.  
  132.         row = last_d[k+1]+1;
  133.         new->link = script[k+1];
  134.         new->op = DELETE;
  135.       }
  136.       else
  137.       {
  138.         /* Move right from the last d-1 on diagonal k-1 */
  139.  
  140.         row = last_d[k-1];
  141.         new->link = script[k-1];
  142.         new->op = INSERT;
  143.       }
  144.  
  145.       /* Code common to the two cases */
  146.  
  147.       new->line1 = row;
  148.       new->line2 = col = row + k - ORIGIN;
  149.       script[k] = new;
  150.  
  151.       /* Slide down the diagonal */
  152.  
  153.       while(row < m && col < n && strcmp(A[row],B[col]) == 0)
  154.       {
  155.         ++row;
  156.         ++col;
  157.       }
  158.       last_d[k] = row;
  159.  
  160.       if(row == m && col == n)
  161.       {
  162.         /* Hit southeast corner, have the answer */
  163.  
  164.         put_scr(script[k]);
  165.         exit(0);
  166.       }
  167.       if(row == m)  /* Hit last row, don't look to left */
  168.         lower = k+2;
  169.       if(col == n)  /* Hit last column, don't look to right */
  170.         upper = k-2;
  171.     }
  172.     --lower;
  173.     ++upper;
  174.   }
  175.   exceed(d);
  176. }
  177.  
  178. /*** Functions ***/
  179.  
  180. /* IN_FILE() - Read in a file and return a count of the lines */
  181.  
  182. int in_file(filename,P)
  183. char *filename,
  184.      *P[];
  185. {
  186.   char buf[100],
  187.        *malloc(),
  188.        *fgets(),
  189.        *save,
  190.        *b;
  191.   FILE *fp,
  192.        *fopen();
  193.   int lines = 0;
  194.  
  195.   if(!(fp = fopen(filename,"r")))
  196.   {
  197.     fprintf(stderr,"Cannot open file %s.\n",filename);
  198.     exit(1);
  199.   }
  200.   while(fgets(buf,100,fp))
  201.   {
  202.     if(lines >= MAXLINES)
  203.       fatal("File is too large for FCOMP.");
  204.     if(!(save = malloc(strlen(buf)+1)))
  205.       fatal("Not enough memory to save the files.");
  206.     P[lines++] = save;
  207.     for(b = buf; *save++ = *b++; )      /* Copy the line */
  208.       ;
  209.   }
  210.   fclose(fp);
  211.   return(lines);
  212. }
  213.  
  214. /* PUT_SCR() - Print the edit script */
  215.  
  216. void put_scr(start)
  217. struct edit *start;
  218. {
  219.   struct edit *ep,
  220.               *behind,
  221.               *ahead,
  222.               *a,
  223.               *b;
  224.   int change;
  225.  
  226.   /* Reverse the pointers */
  227.  
  228.   ahead = start;
  229.   ep = NULL;
  230.   while(ahead)
  231.   {
  232.     behind = ep;
  233.     ep = ahead;
  234.     ahead = ahead->link;
  235.     ep->link = behind;  /* Flip the pointer */
  236.   }
  237.  
  238.   /* Print the commands */
  239.  
  240.   while(ep)
  241.   {
  242.     b = ep;
  243.     if(ep->op == INSERT)
  244.       printf("Inserted after line %d:\n",ep->line1);
  245.     else
  246.     {
  247.       do        /* DELETE */
  248.       {
  249.         /* Look for a block of consecutive deleted lines */
  250.  
  251.         a = b;
  252.         b = b->link;
  253.       }
  254.       while(b && b->op == DELETE && b->line1 == a->line1 + 1);
  255.  
  256.       /* Now b points to the command after the last deletion */
  257.  
  258.       if(change = (b && b->op == INSERT && b->line1 == a->line1))
  259.         printf("Changed ");
  260.       else
  261.         printf("Deleted ");
  262.  
  263.       if(a == ep)
  264.         printf("line %d:\n",ep->line1);
  265.       else
  266.         printf("lines %d-%d:\n",ep->line1,a->line1);
  267.  
  268.       /* Print the deleted lines */
  269.  
  270.       do
  271.       {
  272.         printf(" %s",A[ep->line1 - 1]);
  273.         ep = ep->link;
  274.       }
  275.       while(ep != b);
  276.       if(!change)
  277.         continue;
  278.       printf("To:\n");
  279.     }
  280.  
  281.     /* Print the inserted lines */
  282.  
  283.     do
  284.     {
  285.       printf(" %s",B[ep->line2 - 1]);
  286.       ep = ep->link;
  287.     }
  288.     while(ep && ep->op == INSERT && ep->line1 == b->line1);
  289.   }
  290. }
  291.  
  292. /* FATAL() - Print error message and die */
  293.  
  294. void fatal(msg)
  295. char *msg;
  296. {
  297.   fprintf(stderr,"%s\n",msg);
  298.   exit(1);
  299. }
  300.  
  301. /* EXCEED() - The difference exceeds "d" */
  302.  
  303. void exceed(d)
  304. int d;
  305. {
  306.   fprintf(stderr,"The files differ in at least %d lines.\n",d);
  307.   exit(1);
  308. }
  309.  
  310. /*** End of FCOMP.C ***/
  311.